package com.cuz.daileetcode;

import java.util.HashMap;

public class Day63 {


    public static class ExpressionEvaluation {

        public static int expressionEvaluationWays2(String str, boolean desired) {
            char[] charArray = str.toCharArray();
            int len = charArray.length;
            //desired 为true
            int[][] trueDp = new int[len][len];
            //desired 为false
            int[][] falseDp = new int[len][len];
            for (int index = 0; index < len; index += 2) {
                //对应递归第一个baseCase
                if (charArray[index] == '0') {
                    trueDp[index][index] = 0;
                    falseDp[index][index] = 1;
                } else {
                    trueDp[index][index] = 1;
                    falseDp[index][index] = 0;
                }
            }
            for (int row = len - 3; row >= 0; row -= 2) {
                for (int col = row + 2; col < len; col += 2) {
                    for (int index = row + 1; index < col; index += 2) {
                        if (charArray[index] == '&') {
                            //true & true =true
                            trueDp[row][col] = trueDp[row][index - 1] * trueDp[index + 1][col];
                            //false & false false&true true&false
                            falseDp[row][col] += falseDp[row][index - 1] * falseDp[index + 1][col];
                            falseDp[row][col] += falseDp[row][index - 1] * trueDp[index + 1][col];
                            falseDp[row][col] += trueDp[row][index - 1] * falseDp[index + 1][col];
                            falseDp[row][col] += trueDp[row][index - 1] * trueDp[index + 1][col];
                        } else if (charArray[index] == '|') {
                            //true|false false |true true|true
                            trueDp[row][col] += trueDp[row][index - 1] * trueDp[index + 1][col];
                            trueDp[row][col] += trueDp[row][index - 1] * falseDp[index + 1][col];
                            trueDp[row][col] += falseDp[row][index - 1] * trueDp[index + 1][col];
                            //false|false
                            falseDp[row][col] = falseDp[row][index - 1] * falseDp[index + 1][col];
                        } else {
                            //true ^ false false ^ true
                            trueDp[row][col] += trueDp[row][index - 1] * falseDp[index + 1][col];
                            trueDp[row][col] += falseDp[row][index - 1] * trueDp[index + 1][col];
                            //true^true flase^false
                            falseDp[row][col] = trueDp[row][index - 1] * trueDp[index + 1][col];
                            falseDp[row][col] = falseDp[row][index - 1] * falseDp[index + 1][col];
                        }
                    }
                }
            }
            if (desired) {
                return trueDp[0][len - 1];
            } else {
                return falseDp[0][len - 1];
            }
        }

        public static int expressionEvaluationWays1(String str, boolean desired) {
            char[] charArray = str.toCharArray();
            return process(charArray, 0, charArray.length - 1, desired);
        }

        /*******
         * left right 不位于逻辑运算符时，
         * left到right间字符任任意部分逻辑运算生成desired的种数
         *
         * left 逻辑运算符号 0or1 。。。。逻辑运算符号x。。。0or 1 逻辑运算符号 0 or 1
         *
         * x作为最后结合的逻辑运算符 最后表达式子产生 desired的种数
         * （left 逻辑运算符号 0or1 。。。。）逻辑运算符号x（。。。0or 1 逻辑运算符号 0 or 1）
         * 继续将继续调用左部分 和 右部分
         *
         * 我们循环遍历每一个逻辑运算符号
         * @param charArray 字符串序列
         * @param left 左边界
         * @param right 有边界
         * @param desired 目标值
         * @return left到right间字符任任意部分逻辑运算生成desired的种数
         */
        private static int process(char[] charArray, int left, int right, boolean desired) {
            //如果 left和right 中只有一个字符
            if (left == right) {
                //我们期望的是true
                if (desired) {
                    if (charArray[left] == '1') {
                        return 1;
                    } else {
                        return 0;
                    }
                } else {
                    //期望false
                    if (charArray[left] == '0') {
                        return 1;
                    } else {
                        return 0;
                    }
                }
            }
            int res = 0;
            //index 位置是逻辑运算符号
            for (int index = left + 1; index <= right - 1; index += 2) {
                //期望 index位置符号作为最后运算的符号 且希望结果是true
                if (desired) {
                    //如果是逻辑与符号
                    if (charArray[index] == '&') {
                        // true & true 才能得到true
                        //左侧是true的种数
                        int leftTrue = process(charArray, left, index - 1, true);
                        //有侧是true的种数
                        int rightTrue = process(charArray, index, right, true);
                        res += leftTrue * rightTrue;
                    } else if (charArray[index] == '|') {
                        //如果是 或  true | false 和 false|true  true|true都是true
                        int leftTrue = process(charArray, left, index - 1, true);
                        int rightTrue = process(charArray, index, right, true);
                        int leftFalse = process(charArray, left, index - 1, false);
                        int rightFalse = process(charArray, index, right, false);
                        res += leftTrue * rightFalse;
                        res += leftFalse * rightTrue;
                        res += leftTrue * rightTrue;
                    } else {
                        //如果是异或
                        //true ^false =true，false^true=true
                        int leftTrue = process(charArray, left, index - 1, true);
                        int rightTrue = process(charArray, index, right, true);
                        int leftFalse = process(charArray, left, index - 1, false);
                        int rightFalse = process(charArray, index, right, false);
                        res += leftTrue * rightFalse;
                        res += leftFalse * rightTrue;
                    }
                } else {
                    //如果期望是false
                    //如果是逻辑与符号
                    if (charArray[index] == '&') {
                        // false & false 能得到false
                        // true & false 能得到false
                        //  false & true 能得到false
                        int leftTrue = process(charArray, left, index - 1, true);
                        int rightTrue = process(charArray, index, right, true);
                        int leftFalse = process(charArray, left, index - 1, false);
                        int rightFalse = process(charArray, index, right, false);
                        res += leftFalse * rightFalse;
                        res += leftTrue * rightFalse;
                        res += leftFalse * rightTrue;
                    } else if (charArray[index] == '|') {
                        // false|false 才能false
                        int leftFalse = process(charArray, left, index - 1, false);
                        int rightFalse = process(charArray, index, right, false);
                        res += leftFalse * rightFalse;
                    } else {
                        //如果是异或
                        //false ^false =true，true^true=true
                        int leftTrue = process(charArray, left, index - 1, true);
                        int rightTrue = process(charArray, index, right, true);
                        int leftFalse = process(charArray, left, index - 1, false);
                        int rightFalse = process(charArray, index, right, false);
                        res += leftTrue * rightTrue;
                        res += leftFalse * rightFalse;
                    }
                }
            }
            return res;
        }
    }


    public static class MinimumEditingCost {
        static int minimumEditingCost(String str1, String str2, int add, int delete, int replace) {
            //str1 编辑成 str2的代价
            char[] charArray1 = str1.toCharArray();
            char[] charArray2 = str2.toCharArray();
            int str1Len = charArray1.length;
            int str2Len = charArray2.length;
            int[][] dp = new int[str1Len + 1][str2Len + 1];
            //dp[i][j] 表示把 str1[0...i]的字符更新为 str2[0....j]的代价
            //为什么dp大小是长度+1 因为0，0表示把两个空串进行编辑的代价 自然是0
            for (int row = 0; row < str1Len + 1; row++) {
                for (int col = 0; col < str2Len + 2; col++) {
                    if (row == 0) {
                        //表示把空串编辑成 str2.subString(0,col)的代价 那么只能增加字符
                        dp[row][col] = col * add;
                        continue;
                    }
                    if (col == 0) {
                        //表示把 str1.subString(0,row)替换成空串的代价 那么就是删除
                        dp[row][col] = row * delete;
                        continue;
                    }
                    //末尾位置相同 那么更新过去只需要把 【0.。。row-1】更新为【0，col-1】
                    if (charArray1[row] == charArray2[col]) {
                        dp[row][col] = dp[row - 1][col - 1];
                    } else {
                        //末尾字符不同 那么需要替换末尾字符
                        dp[row][col] = dp[row - 1][col - 1] + replace;
                    }
                    //把 0。。row-1 编辑成 0.。。col 然后删除row 末尾的字符
                    int deleteLast = dp[row - 1][col] + delete;
                    //把 0。。row 编辑成 0.。。col-1 然后增加末尾字符
                    int addLast = dp[row][col - 1] + add;
                    int min = Math.min(deleteLast, addLast);
                    dp[row][col] = Math.min(min, dp[row][col]);
                }
            }
            return dp[str1Len][str2Len];
        }

    }

    public static class LengthOfLongestSubstringWithoutRepeatedCharacters {
        public static int solution1(String str1) {
            HashMap<Character, Integer> preIndex = new HashMap<>();
            int maxLen = 0;
            int preCharLen = -1;
            int curCharLen = 0;
            char[] charArray = str1.toCharArray();
            for (int index = 0; index < charArray.length; index++) {
                //
                preCharLen = Math.max(preCharLen,//上一个字符作为结尾最远到达哪儿
                        //当前字符 之前在那个地方出现过
                        preIndex.getOrDefault(charArray[index], -1));
                //当前字符等于index-瓶颈
                curCharLen = index - preCharLen;
                //更新
                maxLen = Math.max(maxLen, curCharLen);
                preIndex.put(charArray[index], index);
            }
            return maxLen;
        }
    }

}
